package features.advance.leetcode.array.medium;

import java.util.Arrays;
import java.util.Stack;

/**
 * @author LIN
 * @date 2021-11-29 17:23
 *
 * 剑指 Offer II 038. 每日温度
 *
 * 难度：中等
 *
 * 请根据每日 气温 列表 temperatures ，重新生成一个列表，要求其对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。
 *
 *
 *
 * 示例 1:
 *
 * 输入: temperatures = [73,74,75,71,69,72,76,73]
 * 输出: [1,1,4,2,1,1,0,0]
 * 示例 2:
 *
 * 输入: temperatures = [30,40,50,60]
 * 输出: [1,1,1,0]
 * 示例 3:
 *
 * 输入: temperatures = [30,60,90]
 * 输出: [1,1,0]
 *
 *
 * 提示：
 *
 * 1 <= temperatures.length <= 105
 * 30 <= temperatures[i] <= 100
 *
 *
 * 注意：本题与主站 739 题相同： https://leetcode-cn.com/problems/daily-temperatures/
 */
public class Offer_2_038 {

    public static void main(String[] args) {
        Solution solution = new Solution() {
        };
        int[] temperatures = {1,2,3};
        int[] res = solution.dailyTemperatures(temperatures);
        System.out.println(Arrays.toString(res));

    }

    static class Solution {
        public int[] dailyTemperatures(int[] temperatures) {
            Stack<Integer> st = new Stack();
            // 栈里存数组元素下标
            int len = temperatures.length;
            int[] a = new int[len];
            for (int i = 0; i < len; i++) {
                int o = temperatures[i];
                while(!st.isEmpty() && temperatures[st.peek()] < o){
                    Integer pop = st.pop();
                    a[pop] = i - pop;
                }
                st.add(i);
            }
            return a;
        }
    }
}
